{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #批量处理任务"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: processTasks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #批量处理任务"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "某实验室计算机待处理任务以 `[start,end,period]` 格式记于二维数组 `tasks`，表示完成该任务的时间范围为起始时间 `start` 至结束时间 `end` 之间，需要计算机投入 `period` 的时长，注意：\n",
    "1. `period` 可为不连续时间\n",
    "2. 首尾时间均包含在内\n",
    "\n",
    "处于开机状态的计算机可同时处理任意多个任务，请返回电脑最少开机多久，可处理完所有任务。\n",
    "\n",
    "**示例 1：**\n",
    ">输入：`tasks = [[1,3,2],[2,5,3],[5,6,2]]`\n",
    ">\n",
    ">输出：`4`\n",
    ">\n",
    ">解释：\n",
    ">tasks[0] 选择时间点 2、3；\n",
    ">tasks[1] 选择时间点 2、3、5；\n",
    ">tasks[2] 选择时间点 5、6；\n",
    ">因此计算机仅需在时间点 2、3、5、6 四个时刻保持开机即可完成任务。\n",
    "\n",
    "**示例 2：**\n",
    ">输入：`tasks = [[2,3,1],[5,5,1],[5,6,2]]`\n",
    ">\n",
    ">输出：`3`\n",
    ">\n",
    ">解释：\n",
    ">tasks[0] 选择时间点 2 或 3；\n",
    ">tasks[1] 选择时间点 5；\n",
    ">tasks[2] 选择时间点 5、6；\n",
    ">因此计算机仅需在时间点 2、5、6 或 3、5、6 三个时刻保持开机即可完成任务。\n",
    "\n",
    "**提示：**\n",
    "- `2 <= tasks.length <= 10^5`\n",
    "- `tasks[i].length == 3`\n",
    "- `0 <= tasks[i][0] <= tasks[i][1] <= 10^9`\n",
    "- `1 <= tasks[i][2] <= tasks[i][1]-tasks[i][0] + 1`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [t3fKg1](https://leetcode.cn/problems/t3fKg1/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [t3fKg1](https://leetcode.cn/problems/t3fKg1/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,3,2],[2,5,3],[5,6,2]]', '[[2,3,1],[5,5,1],[5,6,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        # Sort tasks by their end time\n",
    "        tasks.sort(key=lambda x: x[1])\n",
    "        \n",
    "        n = len(tasks)\n",
    "        \n",
    "        # Initialize variables\n",
    "        m = 1\n",
    "        sum_time = [0]\n",
    "        tl = [0]\n",
    "        tr = [-1]\n",
    "        \n",
    "        for i in range(n):\n",
    "            l, r = 1, m\n",
    "            start, end, period = tasks[i]\n",
    "            \n",
    "            # Binary search to find the closest smaller end time\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if start <= tr[mid]:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            \n",
    "            # Calculate the parallel time that can be used for the current task\n",
    "            if l < m:\n",
    "                period = max(0, period - (sum_time[m - 1] - sum_time[l]) - (tr[l] - max(tl[l], start) + 1))\n",
    "            \n",
    "            # Update the task\n",
    "            tasks[i][2] = period\n",
    "            \n",
    "            # If the remaining time is zero, continue to the next task\n",
    "            if period == 0:\n",
    "                continue\n",
    "            \n",
    "            # Add time for the current task\n",
    "            while m > 0:\n",
    "                if period <= end - tr[m - 1]:\n",
    "                    tl.append(end - period + 1)\n",
    "                    tr.append(end)\n",
    "                    sum_time.append(sum_time[m - 1] + period)\n",
    "                    m += 1\n",
    "                    break\n",
    "                    \n",
    "                period += tr[m - 1] - tl[m - 1] + 1\n",
    "                m -= 1\n",
    "                tl.pop()\n",
    "                tr.pop()\n",
    "                sum_time.pop()\n",
    "        \n",
    "        return sum_time[m - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda x: x[1])\n",
    "        n = len(tasks)   \n",
    "        m = 1\n",
    "        sum_time = [0]\n",
    "        tl = [0]\n",
    "        tr = [-1]\n",
    "        for i in range(n):\n",
    "            l, r = 1, m\n",
    "            start, end, period = tasks[i]\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if start <= tr[mid]:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if l < m:\n",
    "                period = max(0, period - (sum_time[m - 1] - sum_time[l]) - (tr[l] - max(tl[l], start) + 1))\n",
    "            tasks[i][2] = period\n",
    "            if period == 0:\n",
    "                continue\n",
    "            while m > 0:\n",
    "                if period <= end - tr[m - 1]:\n",
    "                    tl.append(end - period + 1)\n",
    "                    tr.append(end)\n",
    "                    sum_time.append(sum_time[m - 1] + period)\n",
    "                    m += 1\n",
    "                    break              \n",
    "                period += tr[m - 1] - tl[m - 1] + 1\n",
    "                m -= 1\n",
    "                tl.pop()\n",
    "                tr.pop()\n",
    "                sum_time.pop()\n",
    "        return sum_time[m - 1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution(object):\n",
    "    def processTasks(self, tasks):\n",
    "        \"\"\"\n",
    "        :type tasks: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        tasks.append([10**9+1,10**9+1,1])\n",
    "        time,q=0,[]\n",
    "        # for start,end,t in sorted(tasks,key=lambda x:x[1]):\n",
    "        for start,end,t in sorted(tasks,key=lambda x:x[0]):\n",
    "            while q and q[0][0]+time<start:\n",
    "                if q[0][0]+time>=q[0][1]:heappop(q)\n",
    "                else:time+=min(q[0][1],start)-(q[0][0]+time)\n",
    "            heappush(q,[end+1-(t+time),end+1])\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution(object):\n",
    "    def processTasks(self, tasks):\n",
    "        \"\"\"\n",
    "        :type tasks: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # tasks.sort(key=lambda x:x[1])\n",
    "        # runs=[False]*(tasks[-1][1]+1)\n",
    "        # for start,end,t in tasks:\n",
    "        #     t-=sum(runs[start:end+1])\n",
    "        #     if t>0:\n",
    "        #         for i in range(end,start-1,-1):\n",
    "        #             if runs[i]:continue\n",
    "        #             runs[i]=True\n",
    "        #             t-=1\n",
    "        #             if t==0:break\n",
    "        # return sum(runs)\n",
    "        # tasks.append([10**9+1,10**9+1])\n",
    "        tasks.append([10**9+1,10**9+1,1])\n",
    "        time,queue=0,[]\n",
    "        for start,end,t in sorted(tasks,key=lambda x:x[0]):\n",
    "            while queue and queue[0][0]+time<start:\n",
    "                if queue[0][0]+time>=queue[0][1]:heappop(queue)#该任务已完成\n",
    "                else:time+=min(queue[0][1],start)-(queue[0][0]+time)\n",
    "            heappush(queue,[end-(t+time)+1,end+1])\n",
    "        return time\n",
    "# class Solution:\n",
    "#     def processTasks(self, tasks) -> int:\n",
    "#         tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵\n",
    "#         res, q = 0, []\n",
    "#         for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :\n",
    "#             while q and q[0][0]+res < s :\n",
    "#                 if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除\n",
    "#                 else : res += min(q[0][1], s) - (q[0][0]+res)\n",
    "#             heapq.heappush(q, [e-p+1-res, e+1])\n",
    "#         return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort()\n",
    "        tasks.append([10 ** 9 + 1, 10 ** 9 + 1, 1])\n",
    "        heap = []\n",
    "        res = 0\n",
    "        for s, e, p in tasks:\n",
    "            while heap and heap[0][0] + res < s:\n",
    "                if heap[0][0] + res >= heap[0][-1]:\n",
    "                    heapq.heappop(heap)\n",
    "                else:\n",
    "                    res += min(s, heap[0][1]) - res - heap[0][0]\n",
    "            heapq.heappush(heap, [e + 1 - p - res, e + 1])\n",
    "        return res \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution(object):\n",
    "    def processTasks(self, tasks):\n",
    "        \"\"\"\n",
    "        :type tasks: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # tasks.sort(key=lambda x:x[1])\n",
    "        # times=[False]*(tasks[-1][1]+1)\n",
    "        # for start,end,t in tasks:\n",
    "        #     t-=sum(times[start:end+1])\n",
    "        #     if t>0:\n",
    "        #         for i in range(end,start-1,-1):\n",
    "        #             if times[i]:continue\n",
    "        #             times[i]=True\n",
    "        #             t-=1\n",
    "        #             if t==0:break\n",
    "        # return sum(times)\n",
    "        # # tasks.append([10**9+1,10**9+1])\n",
    "        tasks.append([10**9+1,10**9+1,1])\n",
    "        time,queue=0,[]\n",
    "        for start,end,t in sorted(tasks,key=lambda x:x[0]):\n",
    "            while queue and queue[0][0]+time<start:\n",
    "                if queue[0][0]+time>=queue[0][1]:heappop(queue)#该任务已完成\n",
    "                else:time+=min(queue[0][1],start)-(queue[0][0]+time)\n",
    "            heappush(queue,[end+1-(t+time),end+1])\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks) -> int:\n",
    "        tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵\n",
    "        res, q = 0, []\n",
    "        for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :\n",
    "            while q and q[0][0]+res < s :\n",
    "                if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除\n",
    "                else : res += min(q[0][1], s) - (q[0][0]+res)\n",
    "            heapq.heappush(q, [e-p+1-res, e+1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks) -> int:\n",
    "        tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵\n",
    "        res, q = 0, []\n",
    "        for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :\n",
    "            while q and q[0][0]+res < s :\n",
    "                if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除\n",
    "                else : res += min(q[0][1], s) - (q[0][0]+res)\n",
    "            heapq.heappush(q, [e-p+1-res, e+1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks) -> int:\n",
    "        tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵\n",
    "        res, q = 0, []\n",
    "        for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :\n",
    "            while q and q[0][0]+res < s :\n",
    "                if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除\n",
    "                else : res += min(q[0][1], s) - (q[0][0]+res)\n",
    "            heapq.heappush(q, [e-p+1-res, e+1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks) -> int:\n",
    "        tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵\n",
    "        res, q = 0, []\n",
    "        for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :\n",
    "            while q and q[0][0]+res < s :\n",
    "                if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除\n",
    "                else : res += min(q[0][1], s) - (q[0][0]+res)\n",
    "            heapq.heappush(q, [e-p+1-res, e+1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "\n",
    "class Solution(object):\n",
    "    def processTasks(self, tasks):\n",
    "        \"\"\"\n",
    "        :type tasks: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # tasks.sort(key=lambda x:x[1])\n",
    "        # times=[False]*(tasks[-1][1]+1)\n",
    "        # for start,end,t in tasks:\n",
    "        #     t-=sum(times[start:end+1])\n",
    "        #     if t>0:\n",
    "        #         for i in range(end,start-1,-1):\n",
    "        #             if times[i]:continue\n",
    "        #             times[i]=True\n",
    "        #             t-=1\n",
    "        #             if t==0:break\n",
    "        # return sum(times)\n",
    "        # # tasks.append([10**9+1,10**9+1])\n",
    "        tasks.append([10**9+1,10**9+1,1])\n",
    "        time,q=0,[]\n",
    "        for start,end,t in sorted(tasks,key=lambda x:x[0]):\n",
    "            while q and q[0][0]+time<start:\n",
    "                if q[0][0]+time>=q[0][1]:heappop(q)#该任务已完成\n",
    "                else:time+=min(q[0][1],start)-(q[0][0]+time)\n",
    "            heappush(q,[end+1-(t+time),end+1])\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.append([10**9+1,10**9+1,1])\n",
    "        r,q = 0,[]\n",
    "        for [s,e,p] in sorted(tasks,key = lambda x:x[0]):\n",
    "            while q and q[0][0] + r < s:\n",
    "                if q[0][0] + r >= q[0][1]:\n",
    "                    heapq.heappop(q)\n",
    "                else:\n",
    "                    r += min(q[0][1],s) - (q[0][0]+r)\n",
    "            heapq.heappush(q,[e-p+1-r,e+1])\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks) -> int:\n",
    "        tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵\n",
    "        res, q = 0, []\n",
    "        for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :\n",
    "            while q and q[0][0]+res < s :\n",
    "                if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除\n",
    "                else : res += min(q[0][1], s) - (q[0][0]+res)\n",
    "            heapq.heappush(q, [e-p+1-res, e+1])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.append([10**9+1, 10**9+1, 1]) #加个哨兵\n",
    "        res, q = 0, []\n",
    "        for [s, e, p] in sorted(tasks, key=lambda x:x[0]) :\n",
    "            while q and q[0][0]+res < s :\n",
    "                if q[0][0]+res >= q[0][1]: heapq.heappop(q) #任务早已完成，移除\n",
    "                else : res += min(q[0][1], s) - (q[0][0]+res)\n",
    "            heapq.heappush(q, [e-p+1-res, e+1])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\n",
    "            print(r,s)\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\n",
    "            if start <= r:  # start 在区间 st[i] 内\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\n",
    "            if d <= 0: continue\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\n",
    "                l, r, _ = st.pop()\n",
    "                d += r - l + 1  # 合并区间\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\n",
    "            if start <= r:  # start 在区间 st[i] 内\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\n",
    "            if d <= 0: continue\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\n",
    "                l, r, _ = st.pop()\n",
    "                d += r - l + 1  # 合并区间\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]\n",
    "\n",
    "\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\r\n",
    "        tasks.sort(key=lambda t: t[1])\r\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\r\n",
    "        for start, end, d in tasks:\r\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\r\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\r\n",
    "            if start <= r:  # start 在区间 st[i] 内\r\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\r\n",
    "            if d <= 0: continue\r\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\r\n",
    "                l, r, _ = st.pop()\r\n",
    "                d += r - l + 1  # 合并区间\r\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\r\n",
    "        return st[-1][2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\n",
    "            if start <= r:  # start 在区间 st[i] 内\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\n",
    "            if d <= 0: continue\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\n",
    "                l, r, _ = st.pop()\n",
    "                d += r - l + 1  # 合并区间\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\n",
    "            if start <= r:  # start 在区间 st[i] 内\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\n",
    "            if d <= 0: continue\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\n",
    "                l, r, _ = st.pop()\n",
    "                d += r - l + 1  # 合并区间\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\n",
    "            if start <= r:  # start 在区间 st[i] 内\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\n",
    "            if d <= 0: continue\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\n",
    "                l, r, _ = st.pop()\n",
    "                d += r - l + 1  # 合并区间\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\n",
    "            if start <= r:  # start 在区间 st[i] 内\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\n",
    "            if d <= 0: continue\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\n",
    "                l, r, _ = st.pop()\n",
    "                d += r - l + 1  # 合并区间\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def processTasks(self, tasks):\n",
    "        \"\"\"\n",
    "        :type tasks: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        tasks.sort(key=lambda d:d[1])\n",
    "        open_list = []\n",
    "        s = []\n",
    "        for x, y, p in tasks:\n",
    "            if open_list and x <= open_list[-1][1]:\n",
    "                l = 0\n",
    "                r = len(open_list) - 1\n",
    "                while l < r:\n",
    "                    mid = (l + r) >> 1\n",
    "                    if open_list[mid][1] >= x:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                \n",
    "                #二分找到[x, y]包含的开机时间，并计算还需要的开机时间p\n",
    "                p -= s[-1] - s[l]\n",
    "                if x <= open_list[l][0]:\n",
    "                    p -= open_list[l][1] - open_list[l][0] + 1\n",
    "                else:\n",
    "                    p-= open_list[l][1] - x + 1\n",
    "                \n",
    "            if p > 0:\n",
    "                #需要新增的开机时间区间为[y - p + 1, y]，如果出现了重合，那么就将其弹出并更新s和p\n",
    "                while open_list and open_list[-1][1] >= y - p + 1:\n",
    "                    s.pop()\n",
    "                    p += open_list[-1][1] - open_list[-1][0] + 1\n",
    "                    open_list.pop()                    \n",
    "                #将新的开机区间加入到open_list并更新s\n",
    "                open_list.append([y - p + 1, y])\n",
    "                if not s:\n",
    "                    s.append(p)\n",
    "                else:\n",
    "                    s.append(s[-1] + p)\n",
    "\n",
    "        return s[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def processTasks(self, tasks: List[List[int]]) -> int:\n",
    "        tasks.sort(key=lambda t: t[1])\n",
    "        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和\n",
    "        for start, end, d in tasks:\n",
    "            _, r, s = st[bisect_left(st, (start,)) - 1]\n",
    "            d -= st[-1][2] - s  # 去掉运行中的时间点\n",
    "            if start <= r:  # start 在区间 st[i] 内\n",
    "                d -= r - start + 1  # 去掉运行中的时间点\n",
    "            if d <= 0: continue\n",
    "            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀\n",
    "                l, r, _ = st.pop()\n",
    "                d += r - l + 1  # 合并区间\n",
    "            st.append((end - d + 1, end, st[-1][2] + d))\n",
    "        return st[-1][2]\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
